﻿#include"myAlgorithm.h"

//一、双指针算法

//1.移动零 https://leetcode.cn/problems/move-zeroes/description/
void moveZeroes(vector<int>& nums) {//将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序
	int fast = 0, slow = -1;
	while (fast < nums.size())
	{
		while (fast < nums.size() && nums[fast] == 0)
		{
			fast++;
		}
		if (fast >= nums.size())
			break;
		slow++;
		swap(nums[fast], nums[slow]);
		fast++;
	}
}
//1.1优化算法
void moveZeroes1(vector<int>& nums) {
	for (int slow = -1, fast = 0; fast < nums.size(); fast++)
	{
		if (nums[fast])
			swap(nums[fast], nums[++slow]);
	}
}


//2.复写零 https://leetcode.cn/problems/duplicate-zeros/description/
void duplicateZeros(vector<int>& arr)
{
	//既然从前往后覆盖会导致错误，那么就不覆盖模仿行为进行操作，获得最后的位置
	int prev = -1, next = 0;
	while (true)
	{
		if (arr[next] == 0)
		{
			prev++;
		}
		prev++;
		if (prev >= arr.size() - 1)
		{
			break;
		}
		next++;
	}
	cout << prev << " " << next << endl;
	if (prev == arr.size())
	{
		next--;
		arr[prev - 1] = 0;
		prev -= 2;
	}
	cout << prev << " " << next << endl;
	while (next >= 0)
	{
		if (arr[next] == 0)
		{
			arr[prev] = arr[next];
			prev--;
		}
		arr[prev--] = arr[next--];
	}
}
//2.1优化写法 2025.10.27回顾时进行的优化写法
void duplicateZeros1(vector<int>& arr) {
	int slow = 0, fast = 0;
	//先找到复写0后的末尾后一个位置
	while (fast < arr.size())
	{
		if (arr[slow] == 0)
			fast++;
		fast++;
		slow++;
	}

	int end = slow - 1, copy = arr.size() - 1;
	//对特殊情况进行处理，当最后一个0只复写一次时
	if (fast == arr.size() + 1 && arr[end] == 0)
	{
		arr[copy] = 0;
		end--;
		copy--;
	}

	//找到末尾后从末尾开始拷贝
	while (end >= 0)
	{
		if (arr[end] == 0)
		{
			arr[copy--] = 0;
			arr[copy--] = 0;
		}
		else
		{
			arr[copy--] = arr[end];
		}
		end--;
	}
}


//3.快乐数 https://leetcode.cn/problems/happy-number/description/
bool isHappy(int n) {//使用快慢双指针来写 证明为什么一定有环用鸽巢原理(复习一下)
	int slow = n, fast = n;
	while (true)
	{
		int count = 0;
		while (slow)
		{
			count += pow((slow % 10), 2);
			slow /= 10;
		}
		slow = count;

		count = 0;
		while (fast)
		{
			count += pow((fast % 10), 2);
			fast /= 10;
		}
		fast = count;

		count = 0;
		while (fast)
		{
			count += pow((fast % 10), 2);
			fast /= 10;
		}
		fast = count;

		if (fast == 1)
		{
			return true;
		}
		if (fast == slow)
		{
			return false;
		}
	}
}
//3.1优化结构 使用快慢双指针来写
int isHappy_getNum(int num){
	int count = 0;
	while (num)
	{
		count += pow((num % 10), 2);
		num /= 10;
	}
	return count;
}
bool isHappy1(int n) {
	int slow = n, fast = n;
	while (true)
	{
		slow = isHappy_getNum(slow);
		fast = isHappy_getNum(fast);
		fast = isHappy_getNum(fast);
		if (fast == 1)
		{
			return true;
		}
		if (fast == slow)
		{
			return false;
		}
	}
}


//4.盛水最多的容器 https://leetcode.cn/problems/container-with-most-water/description/
int maxArea(vector<int>& height)//1.暴力枚举(时间超限)
{
	int max = 0;
	for (int i = 0; i < height.size(); i++)
	{
		for (int j = i + 1; j < height.size(); j++)
		{
			int h = height[i] > height[j] ? height[j] : height[i];
			int size = h * (j - i);
			if (size > max)
			{
				max = size;
			}
		}
	}
	return max;
}
//4.1优化算法 使用单调分组获取每组最大值在进行比较这些最大值
int maxArea1(vector<int>& height) {
	int left = 0, right = height.size() - 1;
	int max = 0, h = 0, w = 0, size = 0;
	while (left < right)
	{
		w = right - left;
		h = height[left] > height[right] ? height[right--] : height[left++];
		size = h * w;
		if (size > max)
		{
			max = size;
		}
	}
	return max;
}


//5.有效的三角形个数 https://leetcode.cn/problems/valid-triangle-number/description/
int triangleNumber(vector<int>& nums)//暴力枚举(时间超限)
{
	int count = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		for (int j = i + 1; j < nums.size(); j++)
		{
			for (int k = j + 1; k < nums.size(); k++)
			{
				//可以将这个比较优化为一次，两小边之和大于第三边
				if (nums[i] + nums[j] > nums[k]\
					&& nums[i] + nums[k] > nums[j]\
					&& nums[k] + nums[j] > nums[i])
				{
					count++;
				}
			}
		}
	}
	return count;
}
//5.1 优化算法 优化一半，内部指针循环从左往右增加(还是不够优化)
int triangleNumber1(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	int left = 0, right = nums.size() - 1;
	int count = 0;
	while (right > 1)
	{
		left = 0;
		while (left < right)
		{
			int tmp = left + 1;
			while (tmp < right)//效率低在这层循环
			{
				if ((nums[tmp] + nums[left]) > nums[right])
				{
					count += (right - tmp);
					break;
				}
				tmp++;
			}
			left++;
		}
		cout << count << endl;
		right--;
	}
	return count;
}

//5.2 再次优化算法 内部指针循环从右向左增加
int triangleNumber2(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	int left = 0, right = nums.size() - 1;
	int count = 0;
	while (right > 1)
	{
		left = 0;
		int tmp = right - 1;
		while (left < tmp)
		{
			if (nums[tmp] + nums[left] > nums[right])
			{
				count += (tmp - left);
				tmp--;
			}
			else
			{
				left++;
			}
		}
		cout << count << endl;
		right--;
	}
	return count;
}


//6.查找总价为目标值的两个商品 https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/
vector<int> twoSum(vector<int>& price, int target)//暴力枚举法(时间超限)
{
	vector<int>v;
	for (int i = 0; i < price.size(); i++)
	{
		for (int j = 0; j < price.size(); j++)
		{
			if (price[i] + price[j] == target)
			{
				v.push_back(price[i]);
				v.push_back(price[j]);
				return v;
			}
		}
	}
	return v;
}
//6.1优化算法 利用单调性分组比较目标值，直到找到相等的值
vector<int> twoSum1(vector<int>& price, int target) {
	vector<int>v;
	int left = 0, right = price.size() - 1;
	while (left < right)
	{
		if (price[left] + price[right] > target)
		{
			right--;
		}
		else if (price[left] + price[right] < target)
		{
			left++;
		}
		else
		{
			v.push_back(price[left]);
			v.push_back(price[right]);
			return v;
		}
	}
	return v;
}


//7.三数之和 https://leetcode.cn/problems/3sum/description/
vector<vector<int>> threeSum(vector<int>& nums)//使用容器去重(效率低)
{
	vector<vector<int>> vv;
	sort(nums.begin(), nums.end());

	int left, right, mid, prev;
	for (right = 2; right < nums.size(); right++)
	{
		left = 0;
		mid = right - 1;
		while (left < mid)
		{
			if (0 < (nums[left] + nums[mid] + nums[right]))
			{
				mid--;
			}
			else if (0 > (nums[left] + nums[mid] + nums[right]))
			{
				left++;
			}
			else
			{
				vv.push_back({ nums[left],nums[mid],nums[right], });
				left++;
			}
		}
	}
	//去重
	set<vector<int>> s;
	for (auto& it : vv)
	{
		s.insert(it);
	}
	vv.clear();
	for (auto& it : s)
	{
		vv.push_back(it);
	}
	return vv;
}
//7.1优化算法
vector<vector<int>> threeSum1(vector<int>& nums)//利用跳过相同数去重
{
	vector<vector<int>> vv;
	sort(nums.begin(), nums.end());
	int left, right = nums.size() - 1, mid, prev, next, tmp;
	while (right > 1)//记住这里要从大范围缩小，如果从小范围扩大的话，会跳过一些值
	{
		left = 0;
		mid = right - 1;
		while (left < mid)
		{
			if (0 < (nums[left] + nums[mid] + nums[right]))
			{
				mid--;
			}
			else if (0 > (nums[left] + nums[mid] + nums[right]))
			{
				left++;
			}
			else
			{
				vv.push_back({ nums[left],nums[mid],nums[right] });
				prev = left;
				next = mid;
				while (left < mid && nums[prev] == nums[left])
				{
					left++;
				}
				while (left < mid && nums[next] == nums[mid])
				{
					mid--;
				}
			}
		}
		tmp = right;
		while ((right < nums.size()) && (nums[tmp] == nums[right]))
		{
			right--;
		}
	}
	return vv;
}


//8.四数之和 https://leetcode.cn/problems/4sum/description/
vector<vector<int>> fourSum(vector<int>& nums, int target) {//解决方法就是将问题简化为多个三数之和问题
	sort(nums.begin(), nums.end());

	vector<vector<int>>vv;
	int left, right;
	for (int i = nums.size() - 1; i > 2;)
	{
		for (int j = i - 1; j > 1;)
		{
			left = 0, right = j - 1;
			while (left < right)
			{
				long long aim = (long long)target - nums[j] - nums[i];
				if (aim < (nums[left] + nums[right]))
					right--;
				else if (aim > (nums[left] + nums[right]))
					left++;
				else
				{
					vv.push_back({ nums[left],nums[right],nums[j],nums[i] });
					right--, left++;
					while (left < right && nums[left] == nums[left - 1]) left++;
					while (left < right && nums[right] == nums[right + 1]) right--;
				}
			}
			j--;
			while (j > 1 && nums[j] == nums[j + 1]) j--;
		}
		i--;
		while (i > 1 && nums[i] == nums[i + 1]) i--;
	}
	return vv;
}



//二、滑动窗口算法

//9.长度最小的子数组 https://leetcode.cn/problems/minimum-size-subarray-sum/description/
int minSubArrayLen(int target, vector<int>& nums) 
{
	int left = 0, right = 0, min = nums.size() + 1, count = nums[0];
	while (right < nums.size() && left <= right)
	{
		if (count >= target)//利用整数数组起始位置相同，长度越长和越大，所以当和已经大于target的时候，left位置到right往后的元素就不需要枚举了
		{
			int tmp = right - left + 1;
			if (min > tmp)
			{
				min = tmp;
			}
			count -= nums[left];
			left++;
		}
		else
		{
			right++;
			if (right >= nums.size())
			{
				break;
			}
			count += nums[right];
		}
	}
	if (min == nums.size() + 1)
		return 0;
	return min;
}


//10.无重复字符的最长子串 https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
int lengthOfLongestSubstring(string s)//暴力枚举，每个字符都往后查看知道遇见重复值结束查看，换下一个字符查看 时间复杂度O(n^2) 
{
	int left = 0, right = 0, len = 0, max = 0;
	while (left < s.size())
	{
		right = left;
		len = 0;
		unordered_set<int> se;
		while (right < s.size())
		{
			if (se.find(s[right]) == se.end())
			{
				se.insert(s[right]);
				len++;
				right++;
				if (len > max) max = len;
			}
			else break;
		}
		left++;
	}
	return max;
}
//10.1优化算法 使用滑动窗口，right指针不要每次都回到left指针位置，left指针也不需要遍历字符串中每一个值
int lengthOfLongestSubstring1(string s) {
	int left = 0, right = 0, len = 0, max = 0;
	unordered_set<int> se;
	while (left < s.size() && right < s.size())
	{
		if (se.find(s[right]) == se.end())
		{
			se.insert(s[right++]);
			len++;
			if (len > max) max = len;
		}
		else
		{
			while (true)
			{
				se.erase(s[left]);
				len--;
				if (s[left] == s[right])
				{
					break;
				}
				left++;
			}
			left++;
		}
	}
	return max;
}


//11.最大连续1的个数 https://leetcode.cn/problems/max-consecutive-ones-iii/description/
int longestOnes(vector<int>& nums, int k) //暴力枚举 时间超限
{
	int left = 0, right = 0, count = 0, max = 0, len = 0;
	for (left = 0; left < nums.size(); left++)
	{
		right = left;
		len = 0;
		count = 0;
		while (right < nums.size())
		{
			if (nums[right] == 0)
			{
				count++;
				if (count > k) break;
			}
			len++;
			right++;
		}

		if (len > max)
		{
			max = len;
		}
	}
	return max;
}
//11.1优化算法 使用滑动窗口right指针不需要每次都跳回left处,让时间复杂度达到O(n)
int longestOnes1(vector<int>& nums, int k) {
	int left = 0, right = 0, count = 0, max = 0, len = 0;
	while (right < nums.size())
	{
		if (nums[right] == 0)
		{
			count++;
			while (count > k)
			{
				if (nums[left++] == 0) count--;
				len--;
			}
		}
		right++;
		len++;
		if (len > max)max = len;
	}
	return max;
}


//12.将X减小到0的最小操作数 https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/
//正难则反(正着直接对左右指针处理很难，我们换思路从中间处理)
int minOperations(vector<int>& nums, int x)//我写的代码还是很混乱，需要进行一些系统性的修改
{
	int left = 0, right = 0, sum = 0, max = 0;
	for (auto& it : nums)
	{
		sum += it;
	}
	int k = sum - x;
	if (k < 0) return -1;
	else if (k == 0) return nums.size();
	sum = 0;
	while (right < nums.size())
	{
		if (sum < k) sum += nums[right++];
		while (sum > k && left < nums.size()) sum -= nums[left++];
		if (sum == k && left < nums.size())
		{
			max = max > right - left ? max : right - left;
			sum -= nums[left++];
		}
	}
	if (max != 0) return nums.size() - max;
	else return -1;
}
//12.1优化结构
int minOperations1(vector<int>& nums, int x) {
	int sum = 0, max = -1;//这里这里设置为-1是为了防止，我们目标值为0(k=sum-x的k)
	for (auto& it : nums)
	{
		sum += it;
	}
	int k = sum - x;
	if (k < 0) return -1;
	for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
	{
		tmp += nums[right];//进窗口
		while (tmp > k) tmp -= nums[left++];//出窗口
		if (tmp == k) max = max > right - left + 1 ? max : right - left + 1;//判断值是否为目标值
	}
	if (max == -1)return -1;
	else return nums.size() - max;
}


//13.水果成篮 https://leetcode.cn/problems/fruit-into-baskets/description/
int totalFruit(vector<int>& fruits) {
	unordered_map<int, int> m;
	int max = -1;
	for (int left = 0, right = 0; right < fruits.size(); right++)
	{
		m[fruits[right]]++;
		while (m.size() > 2)
		{
			if (--m[fruits[left]] == 0)//注意这里是减为0时需要进行erase
			{
				m.erase(fruits[left]);
			}
			left++;
		}
		max = max > right - left + 1 ? max : right - left + 1;
	}
	return max;
}
//13.1优化算法，将hash表修改为数组不需要容器来提我们维护
int totalFruit1(vector<int>& fruits) {
	int m[100001] = { 0 };
	int max = -1;
	for (int left = 0, right = 0, kind = 0; right < fruits.size(); right++)
	{
		if (m[fruits[right]] == 0) kind++;
		m[fruits[right]]++;
		while (kind > 2)
		{
			if (--m[fruits[left]] == 0)
			{
				kind--;
			}
			left++;
		}
		max = max > right - left + 1 ? max : right - left + 1;
	}
	return max;
}


//14.找到字符串中所有字母异位词 https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/
vector<int> findAnagrams(string s, string p) {
	unordered_map<char, int> m1;
	unordered_map<char, int> m2;
	for (auto& it : p)
	{
		m2[it]++;
	}
	vector<int> v;
	int left = 0, right = 0, len = 0;
	while (right < s.size())
	{
		m1[s[right]]++;
		len = right - left + 1;
		if (len > p.size())
		{
			m1[s[left]]--;
			if (m1[s[left]] == 0) m1.erase(s[left]);
			len--, left++;
		}
		if (len == p.size())
		{
			int count = 0;
			for (auto& it : m1)
			{
				auto tmp = m2.find(it.first);
				if (tmp != m2.end())
				{
					if (tmp->second != it.second) break;
					else count += tmp->second;
				}
				else
				{
					break;
				}
			}
			if (count == p.size()) v.push_back(left);
		}
		right++;
	}
	return v;
}
//14.1 优化算法
vector<int> findAnagrams1(string s, string p) {
	vector<int>v;
	unordered_map<char, int> window;
	unordered_map<char, int> key;
	for (auto it : p)//初始化需要匹配的字符串
	{
		key[it]++;
	}
	int left = 0, right = 0, len = 0;
	while (right < s.size())
	{
		window[s[right++]]++;
		len = right - left;
		if (len > p.size())
		{
			window[s[left]]--;
			if (window[s[left]] == 0) window.erase(s[left]);
			left++;
		}
		if (right - left == p.size() && window == key) {
			v.push_back(left);
		}
	}
	return v;
}


//15.串联所有单词的子串 https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/
vector<int> findSubstring(string s, vector<string>& words) {
	unordered_map<string, int> wordMap;
	vector<int> v;
	//存放所有的单词
	for (auto& it : words)
	{
		wordMap[it]++;
	}
	int wordLen = words[0].size();
	for (int offset = 0; offset < wordLen; offset++)
	{
		unordered_map<string, int> window;
		int windowSize = 0;
		int left = offset, right = offset;
		while (right + wordLen <= s.size())
		{
			string tmp = s.substr(right, wordLen);
			right += wordLen;
			window[tmp]++;
			windowSize++;
			//窗口太大要移动左指针了
			if (windowSize > words.size())
			{
				tmp = s.substr(left, wordLen);
				left += wordLen;
				windowSize--;
				window[tmp]--;
				if (window[tmp] == 0) window.erase(tmp);
			}

			if (window == wordMap)
			{
				v.push_back(left);
			}
		}
	}
	return v;
}


//16.最小覆盖子串 https://leetcode.cn/problems/minimum-window-substring/description/
string minWindow(string s, string t) {
	// key 记录 t 中每个字符需要的数量
	unordered_map<char, int> key;
	for (auto it : t)
	{
		key[it]++;
	}
	// window 记录当前窗口中每个字符的数量
	unordered_map<char, int> window;
	int left = 0, right = 0, minLen = INT_MAX, start = 0;
	// valid 记录当前窗口中有多少个字符已经满足要求
	// 当 valid == key.size() 时，说明窗口已经包含所有需要的字符
	int valid = 0;
	while (right < s.size())
	{
		//如果右指针指向的值为key中数据，那么就可以放入window中
		char ch = s[right++];
		if (key.count(ch))
		{
			window[ch]++;
			if (window[ch] == key[ch]) valid++;
		}
		//如果我们窗口中的元素满足了要求，这个时候就可以减小窗口来找最小字符
		while (valid == key.size())
		{
			if (minLen > right - left)
			{
				minLen = right - left;
				start = left;
			}
			ch = s[left++];
			if (window.count(ch))
			{
				window[ch]--;
				if (window[ch] < key[ch]) valid--;
			}
		}
	}
	return minLen == INT_MAX ? "" : s.substr(start, minLen);
}



//三、二分查找算法

//17.二分查找 https://leetcode.cn/problems/binary-search/description/
int search(vector<int>& nums, int target) {
	int left = 0, right = nums.size() - 1;
	while (left <= right)
	{
		int mid = (right + left) / 2;
		if (nums[mid] > target)
		{
			right = mid - 1;
		}
		else if (nums[mid] < target)
		{
			left = mid + 1;
		}
		else {
			return mid;
		}
	}
	return -1;
}


//18.在排序数组中查找元素的第一个和最后一个位置 
//https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
vector<int> searchRange(vector<int>& nums, int target) {
	if (nums.empty()) return { -1,-1 };
	int left = 0, right = nums.size() - 1, mid = -1, lPTarget = -1, rPTarget = -1;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (nums[mid] >= target)
		{
			if (nums[mid] == target) lPTarget = mid;
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	left = 0, right = nums.size() - 1, mid = -1;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (nums[mid] <= target)
		{
			if (nums[mid] == target) rPTarget = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return { lPTarget,rPTarget };
}


//19.搜索插入位置 https://leetcode.cn/problems/search-insert-position/description/
int searchInsert(vector<int>& nums, int target) {
	int left = 0, right = nums.size() - 1, mid = 0;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (nums[mid] > target)
		{
			right = mid - 1;
			if (mid - 1 < 0 || nums[mid - 1] < target)
				return mid;
		}
		else if (nums[mid] < target)
		{
			left = mid + 1;
			if (mid + 1 >= nums.size() || nums[mid + 1] > target)
				return mid + 1;
		}
		else {
			return mid;
		}
	}
	return 0;
}


//20.x 的平方根 https://leetcode.cn/problems/sqrtx/description/
int mySqrt(int x) {
	int left = 0, right = x;
	while (left <= right)
	{
		long long mid = (left + right) / 2;
		if (mid * mid > x)
		{
			if ((mid - 1) * (mid - 1) < x)
				return mid - 1;
			right = mid - 1;
		}
		else if (mid * mid < x)
		{
			if ((mid + 1) * (mid + 1) > x)
				return mid;
			left = mid + 1;
		}
		else {
			return mid;
		}
	}
	return 0;
}


//21.山脉数组的峰顶索引 https://leetcode.cn/problems/peak-index-in-a-mountain-array/description/
int peakIndexInMountainArray(vector<int>& arr) {
	int left = 0, right = arr.size() - 1, mid = 0;
	while (left < right)
	{
		mid = (left + right) / 2;
		if (mid + 1 < arr.size() && arr[mid] < arr[mid + 1])//递增
		{
			left = mid + 1;
		}
		else//递减
		{
			right = mid;
		}
	}
	return left;
}

//22.寻找峰值 https://leetcode.cn/problems/find-peak-element/description/
int findPeakElement(vector<int>& nums) {
	int left = 0, right = nums.size() - 1;
	while (left < right)
	{
		int mid = (left + right) / 2;
		if (mid + 1 < nums.size() && nums[mid] > nums[mid + 1])
		{
			right = mid;
		}
		else
		{
			left = mid + 1;
		}
	}
	return left;
}

//23.寻找旋转排序数组中的最小值 https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/
int findMin(vector<int>& nums) {
	int left = 0, right = nums.size() - 1, mid = 0;
	while (left < right)
	{
		mid = (left + right) / 2;
		if (nums[mid] > nums[right])
		{
			left = mid + 1;
		}
		else
		{
			right = mid;
		}
	}
	return nums[left];
}

//24.点名 https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/
int takeAttendance(vector<int>& records) {
	int left = 0, right = records.size() - 1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (records[mid] != mid)
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	return left;
}



//四、前缀和算法

//25.【模板】前缀和 https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?tpId=230&tqId=2021480&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
class solution_getSum
{
public:
	void getSum()
	{
		int m, n;
		vector<long long> v;
		cin >> n >> m;
		long long sum = 0;
		v.push_back(sum);
		for (int i = 0; i < n; i++)
		{
			int num;
			scanf("%d", &num);
			sum += num;
			v.push_back(sum);
		}
		for (int i = 0; i < m; i++)
		{
			int l, r;
			scanf("%d%d", &l, &r);
			printf("%lld\n", v[r] - v[l - 1]);
		}
	}
};

//26.【模板】二维前缀和 https://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc?tpId=230&tqId=2023819&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
class solution_two_dimension_sum {
public:
	void two_dimension_sum()
	{
		int n, m, q;
		vector<vector<long long>>vv;
		scanf("%d%d%d", &n, &m, &q);
		//构造二维数组
		for (int i = 0; i <= n; i++)
		{
			vector<long long> v;
			for (int j = 0; j <= m; j++)
			{
				if (i == 0 || j == 0) {
					v.push_back(0);
				}
				else {
					long long tmp = 0, sum = v[j - 1] + vv[i - 1][j] - vv[i - 1][j - 1];
					scanf("%lld", &tmp);
					sum += tmp;
					v.push_back(sum);
				}
			}
			vv.push_back(v);
		}
		//开始计算机子矩阵和
		for (int i = 0; i < q; i++)
		{
			int x1, x2, y1, y2;
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			printf("%lld\n", vv[x2][y2] - vv[x2][y1 - 1] - vv[x1 - 1][y2] + vv[x1 - 1][y1 - 1]);
		}
	}
};

//27.寻找数组的中心下标 https://leetcode.cn/problems/find-pivot-index/description/
int pivotIndex(vector<int>& nums) {
	vector<int> sum;
	sum.push_back(nums[0]);
	for (int i = 1; i < nums.size(); i++)
	{
		sum.push_back(sum[i - 1] + nums[i]);
	}
	int left = 0, right = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		if (i == 0) left = 0;
		else left = sum[i - 1];
		if (i == nums.size() - 1) right = 0;
		else right = sum[nums.size() - 1] - sum[i];
		if (left == right)
			return i;
	}
	return -1;
}

//28.除自身以外数组的乘积 https://leetcode.cn/problems/product-of-array-except-self/description/
vector<int> productExceptSelf(vector<int>& nums) {
	vector<int>v;
	vector<int>left(nums.size(), 1);
	vector<int>right(nums.size(), 1);
	for (int i = 1; i < nums.size(); i++)
	{
		left[i] = left[i - 1] * nums[i - 1];
	}
	for (int i = nums.size() - 2; i >= 0; i--)
	{
		right[i] = right[i + 1] * nums[i + 1];
	}
	for (int i = 0; i < nums.size(); i++)
	{
		v.push_back(left[i] * right[i]);
	}
	return v;
}
//28.1优化算法空间复杂度为O(1)
vector<int> productExceptSelf1(vector<int>& nums) {
	vector<int>v(nums.size(), 1);
	for (int i = 1; i < nums.size(); i++)
	{
		v[i] = v[i - 1] * nums[i - 1];
	}
	int product = 1;
	for (int i = nums.size() - 1; i >= 0; i--)
	{
		v[i] *= product;
		product *= nums[i];
	}
	return v;
}

//29.和为 K 的子数组 https://leetcode.cn/problems/subarray-sum-equals-k/description/
int subarraySum(vector<int>& nums, int k) {
	unordered_map<int, int> m;
	m[0] = 1;
	int sum = 0, count = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		sum += nums[i];
		if (m.count(sum - k)) count += m[sum - k];
		m[sum]++;
	}
	return count;
}

//30.和可被 K 整除的子数组 https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/
int subarraysDivByK(vector<int>& nums, int k) {
	unordered_map<int, int> m;
	int sum = 0, count = 0;
	m[0]++;
	for (int i = 0; i < nums.size(); i++)
	{
		sum += nums[i];
		int remainder = (sum % k + k) % k;
		if (m.count(remainder)) count += m[remainder];
		m[remainder]++;
	}
	return count;
}

//31.连续数组 https://leetcode.cn/problems/contiguous-array/description/
int findMaxLength(vector<int>& nums) {
	unordered_map<int, int> m;
	m[0] = -1;
	int sum = 0, maxLen = 0, count = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		sum += nums[i] == 0 ? -1 : 1;
		if (m.count(sum))
		{
			count = i - m[sum];
			maxLen = max(maxLen, count);
		}
		else
		{
			m[sum] = i;
		}
	}
	return maxLen;
}

//32.矩阵区域和 https://leetcode.cn/problems/matrix-block-sum/description/
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
	vector<vector<int>> vv;
	int row = mat.size(), col = mat[0].size();
	for (int i = 0; i <= row; i++)
	{
		vector<int> v;
		for (int j = 0; j <= col; j++)
		{
			if (j == 0 || i == 0) { v.push_back(0); }
			else {
				int sum = mat[i - 1][j - 1] + v[j - 1] + vv[i - 1][j] - vv[i - 1][j - 1];
				v.push_back(sum);
			}
		}
		vv.push_back(v);
	}
	vector<vector<int>> answer;
	for (int i = 1; i <= row; i++)
	{
		vector<int> v;
		for (int j = 1; j <= col; j++)
		{
			int bigi = i + k, bigj = j + k, smalli = i - k - 1, smallj = j - k - 1;
			if (bigi > row) bigi = row;
			if (bigj > col) bigj = col;
			if (smalli < 0) smalli = 0;
			if (smallj < 0) smallj = 0;
			v.push_back(vv[bigi][bigj] - vv[smalli][bigj] - vv[bigi][smallj] + vv[smalli][smallj]);
		}
		answer.push_back(v);
	}
	return vv;
}
//32.1优化提前开空间
vector<vector<int>> matrixBlockSum1(vector<vector<int>>& mat, int k) {
	int row = mat.size(), col = mat[0].size();
	vector<vector<int>> vv(row + 1, vector<int>(col + 1));
	for (int i = 0; i <= row; i++)
	{

		for (int j = 0; j <= col; j++)
		{
			if (j == 0 || i == 0) { vv[i][j] = 0; }
			else {
				vv[i][j] = mat[i - 1][j - 1] + vv[i][j - 1] + vv[i - 1][j] - vv[i - 1][j - 1];
			}
		}
	}
	vector<vector<int>> answer(row, vector<int>(col));
	for (int i = 1; i <= row; i++)
	{
		for (int j = 1; j <= col; j++)
		{
			int bigi = i + k, bigj = j + k, smalli = i - k - 1, smallj = j - k - 1;
			if (bigi > row) bigi = row;
			if (bigj > col) bigj = col;
			if (smalli < 0) smalli = 0;
			if (smallj < 0) smallj = 0;
			answer[i - 1][j - 1] = vv[bigi][bigj] - vv[smalli][bigj] - vv[bigi][smallj] + vv[smalli][smallj];
		}
	}
	return answer;
}



//五、位运算

//33.判定字符是否唯一 https://leetcode.cn/problems/is-unique-lcci/description/
bool isUnique(string astr) {
	unordered_map<char, int> m;
	for (auto ch : astr)
	{
		if (m.count(ch)) return false;
		m[ch]++;
	}
	return true;
}
//33.1极致优化空间
bool isUnique1(string astr) {
	int bitmap = 0;
	for (auto it : astr)
	{
		int pos = it - 'a';
		if (bitmap & (1 << pos))
			return false;
		bitmap |= (1 << pos);
	}
	return true;
}

//34.丢失的数字 https://leetcode.cn/problems/missing-number/description/
int missingNumber(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	for (int i = 0; i < nums.size(); i++)
	{
		if (nums[i] != i)
			return i;
	}
	return nums.size();
}
//34.1 利用做差的方式找缺失数
int missingNumber1(vector<int>& nums) {
	int count = nums.size() + 1;
	int sum = (count - 1) * count / 2;
	int smallSum = 0;
	for (auto it : nums)
	{
		smallSum += it;
	}
	return sum - smallSum;
}
//34.2 做差法防溢出
int missingNumber2(vector<int>& nums) {
	int num = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		num += (i + 1) - nums[i];
	}
	return num;
}
//34.3 异或法
int missingNumber3(vector<int>& nums) {
	int num = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		num ^= nums[i] ^ (i + 1);
	}
	return num;
}

//35.两整数之和 https://leetcode.cn/problems/sum-of-two-integers/description/
int getSum(int a, int b) {//模拟运算法
	int prev = 0, num = 0;
	for (int i = 0; i < 32; i++)
	{
		int tmp1 = (a >> i) & 1;
		int tmp2 = (b >> i) & 1;
		if (tmp1 == 1 && tmp2 == 1)
		{
			num |= (prev << i);
			prev = 1;
		}
		else if (tmp1 == 1 || tmp2 == 1)
		{
			if (prev == 0) num |= (1 << i);
			else prev = 1;
		}
		else
		{
			if (prev == 1) num |= (1 << i);
			prev = 0;
		}
	}
	return num;
}
//35.1 使用异或方法
int getSum1(int a, int b) {
	int prev = 0, num = 0;
	for (int i = 0; i < 32; i++)
	{
		int tmp1 = (a >> i) & 1;
		int tmp2 = (b >> i) & 1;
		int curBit = tmp1 ^ tmp2 ^ prev;
		num |= (curBit << i);
		prev = (tmp1 & tmp2) | (tmp1 & prev) | (tmp2 & prev);
	}
	return num;
}
//35.2迭代进位法 所有位置同时计算进位直到进位为0则计算完成
int getSum2(int a, int b) {
	int carry = b, num = a;
	while (carry != 0)
	{
		int tmp = (num & carry) << 1;//计算新进位
		num = num ^ carry;//计算非进位数
		carry = tmp;//赋值新进位
	}
	return num;
}

//36.只出现一次的数字 II https://leetcode.cn/problems/single-number-ii/description/
int singleNumber(vector<int>& nums) {//hash映射法
	unordered_map<int, int> m;
	for (auto it : nums)
	{
		m[it]++;
	}
	for (auto it : m)
	{
		if (it.second == 1)
			return it.first;
	}
	return 0;
}
//36.1 数学推导法,只出现一次的数，在所有数相加后的每个位%3都等于1，由这个1可以推导出这个数的比特位分布
class Solution {
public:
	int singleNumber(vector<int>& nums) {
		int answer = 0;
		for (int i = 0; i < 32; i++)
		{
			int count = 0;
			for (auto it : nums)
			{
				count += (it >> i) & 1;
			}
			answer |= ((count % 3) << i);
		}
		return answer;
	}
};
//36.2 状态机方法
int singleNumber2(vector<int>& nums) {
	int ones = 0, twos = 0;
	for (auto it : nums)
	{
		twos |= it & ones;
		ones ^= it;
		int threes = ones & twos;
		ones &= ~threes;
		twos &= ~threes;
	}
	return ones;
}

//37.消失的两个数字 https://leetcode.cn/problems/missing-two-lcci/description/
vector<int> missingTwo(vector<int>& nums) {
	//获得两个消失数的异或
	int twoSor = 0;
	int i = 0;
	for (; i < nums.size(); i++)
	{
		twoSor ^= nums[i] ^ i;
	}
	twoSor ^= i ^ (i + 1) ^ (i + 2);

	//找到两个数不同的一个位
	int pos = 0;
	for (i = 0; i < 32; i++)
	{
		if (twoSor & (1 << i)) {
			pos = i;
			break;
		}
	}

	//开始分组，完整数组和程序给出数组要分开异或
	int group1 = 0, group2 = 0;
	for (i = 0; i < nums.size(); i++)
	{
		if (nums[i] & (1 << pos)) group1 ^= nums[i];
		else group2 ^= nums[i];
	}
	for (i = 1; i <= nums.size() + 2; i++)
	{
		if (i & (1 << pos)) group1 ^= i;
		else group2 ^= i;
	}
	return { group1,group2 };
}



//六、模拟

//38.替换所有的问号 https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/description/
string modifyString(string s) {
	vector<char> v = { 'a','b','c' };
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == '?')
		{
			char prev = ' ', next = ' ';
			if (i - 1 >= 0) prev = s[i - 1];
			if (i + 1 < s.size()) next = s[i + 1];
			for (auto it : v)
			{
				if (it != prev && it != next)
				{
					s[i] = it;
					break;
				}
			}
		}
	}
	return s;
}


//39.提莫攻击 https://leetcode.cn/problems/teemo-attacking/description/
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
	int count = 0;
	for (int i = 0; i < timeSeries.size(); i++)
	{
		count += duration;
		if (i > 0 && (duration + timeSeries[i - 1]) > timeSeries[i])
			count -= duration + timeSeries[i - 1] - timeSeries[i];
	}
	return count;
}

//40.Z 字形变换 https://leetcode.cn/problems/zigzag-conversion/description/
string convert(string s, int numRows) {
	if (numRows == 1 || s.size() <= numRows) return s;
	vector<string> v(numRows);
	bool toword = true;//true为向上false为向下
	int row = 0;
	for (int i = 0; i < s.size(); i++)
	{
		v[row] += s[i];
		if (row == numRows - 1 || row == 0) toword = !toword;
		row += toword ? -1 : 1;
	}
	string format;
	for (auto it : v)
	{
		format += it;
	}
	return format;
}

//41.外观数列 https://leetcode.cn/problems/count-and-say/description/
string countAndSay(int n) {
	if (n == 1) return "1";
	string s = countAndSay(n - 1);
	string news;
	int count = 1;
	for (int i = 0; i < s.size(); i++)
	{
		if (i + 1 < s.size() && s[i] == s[i + 1]) count++;
		else {
			news += '0' + count;
			news += s[i];
			count = 1;
		}
	}
	return news;
}

//42.数青蛙 https://leetcode.cn/problems/minimum-number-of-frogs-croaking/description/
int minNumberOfFrogs(string croakOfFrogs) {
	int c = 0, r = 0, o = 0, a = 0, k = 0, count = 0, maxc;
	for (int i = 0; i < croakOfFrogs.size(); i++)
	{
		if (croakOfFrogs[i] == 'c') {
			c++;
			count++;
			maxc = max(count, maxc);
		}
		if (croakOfFrogs[i] == 'r') {
			r++;
			if (r > c) return -1;
		}
		if (croakOfFrogs[i] == 'o') {
			o++;
			if (o > r) return -1;
		}
		if (croakOfFrogs[i] == 'a') {
			a++;
			if (a > o) return -1;
		}
		if (croakOfFrogs[i] == 'k') {
			k++;
			count--;
			if (k > a) return -1;
			c--, r--, o--, a--, k--;
		}
	}
	if (c == r && r == o && o == a && a == k) return maxc;
	else return -1;
}



//七、分治 - 快速排序

//43.颜色分类 https://leetcode.cn/problems/sort-colors/description/
void sortColors(vector<int>& nums) {//简单排序
	for (int i = 0; i < nums.size() - 1; i++)
	{
		for (int j = 1; j < nums.size(); j++)
		{
			if (nums[j - 1] > nums[j]) swap(nums[j], nums[j - 1]);
		}
	}
}
//43.1计数排序
void sortColors1(vector<int>& nums) {
	int zero = 0, one = 0, two = 0;
	for (auto it : nums)
	{
		switch (it) {
		case 0:
			zero++;
			break;
		case 1:
			one++;
			break;
		case 2:
			two++;
			break;
		}
	}
	for (int i = 0; i < nums.size(); i++)
	{
		if (zero > 0) { nums[i] = 0; zero--; }
		else if (one > 0) { nums[i] = 1; one--; }
		else { nums[i] = 2; two--; }
	}
}
//43.2三指针/荷兰国旗算法
void sortColors2(vector<int>& nums) {
	int left = 0, right = nums.size();
	for (int i = 0; i < right; i++)
	{
		if (nums[i] == 0) swap(nums[i], nums[left++]);
		else if (nums[i] == 2) swap(nums[i], nums[right--]);
	}
}

//44.排序数组 https://leetcode.cn/problems/sort-an-array/description/
class sortArray_Solution {//随机值快排
public:
	void sort_sortArray(int left, int right, vector<int>& nums)
	{
		if (left >= right) return;
		int pivot_idx = left + rand() % (right - left + 1);
		swap(nums[pivot_idx], nums[left]);
		int target = nums[left];
		int posl = left, posr = right;
		while (left < right)
		{
			while (left < right && nums[right] >= target) right--;
			while (left < right && nums[left] <= target) left++;
			if (left < right) swap(nums[left], nums[right]);
		}
		swap(nums[posl], nums[left]);

		sort_sortArray(posl, left - 1, nums);
		sort_sortArray(left + 1, posr, nums);
	}

	vector<int> sortArray(vector<int>& nums) {
		srand((unsigned int)time(nullptr));
		sort_sortArray(0, nums.size() - 1, nums);
		return nums;
	}
};

